/* MergeSort.java, adapted from ListSorts.java in HW8 */
package mergesort;
import list.*;

public class MergeSort {

	/**
	 *  makeQueueOfQueues() makes a queue of queues, each containing one item
	 *  of q.  Upon completion of this method, q is empty.
	 *  @param q is a LinkedQueue of objects.
	 *  @return a LinkedQueue containing LinkedQueue objects, each of which
	 *    contains one object from q.
	 **/
	public static LinkedQueue makeQueueOfQueues(LinkedQueue q) {
		LinkedQueue queueContainer = new LinkedQueue();
		while (!q.isEmpty()) {
			try {
				LinkedQueue newQueue = new LinkedQueue();
				newQueue.enqueue(q.dequeue());
				queueContainer.enqueue(newQueue);
			} catch (QueueEmptyException e) {
				System.err.println(e);
			}
		}
		return queueContainer;
	}

	/**
	 *  mergeSortedQueues() merges two sorted queues into a third.  On completion
	 *  of this method, q1 and q2 are empty, and their items have been merged
	 *  into the returned queue.
	 *  @param q1 is LinkedQueue of Comparable objects, sorted from smallest 
	 *    to largest.
	 *  @param q2 is LinkedQueue of Comparable objects, sorted from smallest 
	 *    to largest.
	 *  @return a LinkedQueue containing all the Comparable objects from q1 
	 *   and q2 (and nothing else), sorted from smallest to largest.
	 **/
	public static LinkedQueue mergeSortedQueues(LinkedQueue q1, LinkedQueue q2) {
		LinkedQueue myQueue = new LinkedQueue();
		while (!q1.isEmpty() && !q2.isEmpty()) {
			try {
				if (((Comparable)(q1.front())).compareTo((Comparable)(q2.front())) < 0) {	// If q1.front < q2.front, dequeue q1 and add to myQueue.
					myQueue.enqueue(q1.dequeue());
				} else {	// Otherwise enqueue q2.front.
					myQueue.enqueue(q2.dequeue());
				}
			} catch (QueueEmptyException e) {
				System.err.println(e);
			}
		}

		if (q1.isEmpty()) {
			myQueue.append(q2);
		} else if (q2.isEmpty()) {
			myQueue.append(q1);
		}

		return myQueue;
	}

	/**
	 *  mergeSort() sorts q from smallest to largest using mergesort.
	 *  @param q is a LinkedQueue of Comparable objects.
	 **/
	public static void mergeSort(LinkedQueue q) {
		if (q.size() <= 1) { return; }
		LinkedQueue containerQueue = makeQueueOfQueues(q);
		try {
			while (containerQueue.size() > 1) {
				LinkedQueue q1 = (LinkedQueue)(containerQueue.dequeue());
				LinkedQueue q2 = (LinkedQueue)(containerQueue.dequeue());
				containerQueue.enqueue(mergeSortedQueues(q1, q2));
			}
			q.append((LinkedQueue)(containerQueue.dequeue()));
		} catch (QueueEmptyException e) {
			System.err.println(e);
		}
	}

	/**
	 *  TESTING PURPOSES ONLY.
	 *  makeRandom() builds a LinkedQueue of the indicated size containing
	 *  Integer items.  The items are randomly chosen between 0 and size - 1.
	 *  @param size is the size of the resulting LinkedQueue.
	 **/
	public static LinkedQueue makeRandom(int size) {
		LinkedQueue q = new LinkedQueue();
		for (int i = 0; i < size; i++) {
			q.enqueue(new Integer((int) (size * Math.random())));
		}
		return q;
	}

	/**
	 * TESTING PURPOSES ONLY.
	 * verify() is a helper function used for testing purposes only.  It 
	 * prints an error message whenever a test fails.
	 * @param invariant
	 * @param message
	 * @author Jonathan Eng
	 */
	public static void verify (boolean invariant, String message) {
		if (!invariant) {
			System.out.println("*** ERROR: " + message);
			Thread.dumpStack();
		}
		else {
			System.out.println("Test passed.");
		}
	}

	/**
	 *  main() performs some tests on mergesort and quicksort.  Feel free to add
	 *  more tests of your own to make sure your algorithms works on boundary
	 *  cases.  Your test code will not be graded.
	 **/
	public static void main(String [] args) {

		LinkedQueue q = makeRandom(10);
		System.out.println(q.toString());
		mergeSort(q);
		System.out.println(q.toString());

		LinkedQueue q1, q2, q3, q4;
		boolean t;
		String result, expected;

		System.out.println("\n== Testing makeQueueOfQueues() ==\tTotal Tests: 3");
		q1 = new LinkedQueue();	// General case.
		for (int i = 1; i <= 5; i++) {
			q1.enqueue(i);
		}
		result = makeQueueOfQueues(q1).toString();
		expected = "[ [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] ]";
		t = (result.equals(expected));
		verify(t, "Queue returned was " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: only 1 element in queue.
		q1.enqueue(0);
		result = makeQueueOfQueues(q1).toString();
		expected = "[ [ 0 ] ]";
		t = (result.equals(expected));
		verify(t, "Queue returned was " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: empty queue.
		result = makeQueueOfQueues(q1).toString();
		expected = "[ ]";
		t = (result.equals(expected));
		verify(t, "Queue returned was " + result + "\nExpected " + expected);

		System.out.println("\n== Testing mergeSortedQueues() == \tTotal Tests: 8");
		q1 = new LinkedQueue();	// Case: Equal length queues.
		for (int i = 1; i <= 5; i++) {
			q1.enqueue(2 * i);
		}
		q2 = new LinkedQueue();
		for (int i = 1; i <= 5; i++) {
			q2.enqueue(2 * i - 1);
		}
		result = mergeSortedQueues(q1, q2).toString();
		expected = "[ 1 2 3 4 5 6 7 8 9 10 ]";
		t = (result.equals(expected));
		verify(t, "Queue was not merged properly: " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: Queue 1 is shorter.	
		for (int i = 1; i <= 5; i++) {
			q1.enqueue(i);
		}
		q2 = new LinkedQueue();
		for (int i = 1; i <= 5; i++) {
			q2.enqueue(2 * i);
		}
		result = mergeSortedQueues(q1, q2).toString();
		expected = "[ 1 2 2 3 4 4 5 6 8 10 ]";
		t = (result.equals(expected));
		verify(t, "Queue was not merged properly: " + result + "\nExpected " + expected);

		q1 = new LinkedQueue(); // Case: Queue 2 is shorter.
		for (int i = 1; i < 10; i+=2) {
			q1.enqueue(i);
		}
		q2 = new LinkedQueue();
		for (int i = 0; i < 10; i+=3) {
			q2.enqueue(i);
		}
		result = mergeSortedQueues(q1, q2).toString();
		expected = "[ 0 1 3 3 5 6 7 9 9 ]";
		t = (result.equals(expected));
		verify(t, "Queue was not merged properly: " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: Queue 1 has 1 item.
		q1.enqueue(0);

		q2 = new LinkedQueue();
		q2.enqueue(0);
		q2.enqueue(1);
		q2.enqueue(2);

		result = mergeSortedQueues(q1,q2).toString();
		expected = "[ 0 0 1 2 ]";
		t = result.equals(expected);
		verify(t, "Queue was not merged properly: " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: Queue 2 has 1 item.
		q1.enqueue(1);
		q1.enqueue(3);
		q1.enqueue(5);

		q2 = new LinkedQueue();
		q2.enqueue(6);

		result = mergeSortedQueues(q1,q2).toString();
		expected = "[ 1 3 5 6 ]";
		t = result.equals(expected);
		verify(t, "Queue was not merged properly: " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: Queue 1 is empty.
		q2 = new LinkedQueue();
		q2.enqueue(1);
		q2.enqueue(2);
		q2.enqueue(3);

		result = mergeSortedQueues(q1,q2).toString();
		expected = "[ 1 2 3 ]";
		t = result.equals(expected);
		verify(t, "Queue was not merged properly: " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: Queue 2 is empty.
		q1.enqueue(-1);
		q1.enqueue(0);
		q2 = new LinkedQueue();

		result = mergeSortedQueues(q1,q2).toString();
		expected = "[ -1 0 ]";
		t = result.equals(expected);
		verify(t, "Queue was not merged properly: " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: Both queues are empty.
		q2 = new LinkedQueue();

		result = mergeSortedQueues(q1,q2).toString();
		expected = "[ ]";
		t = result.equals(expected);
		verify(t, "Queue was not merged properly: " + result + "\nExpected " + expected);

		System.out.println("\n== Testing mergeSort() ==\tTotal Tests: 2");
		q1 = new LinkedQueue();	// Case: Empty queue.
		mergeSort(q1);
		result = q1.toString();
		expected = "[ ]";
		t = result.equals(expected);
		verify(t, "Queue was not mergeSorted properly: " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: Length-1 queue.
		q1.enqueue(1);
		mergeSort(q1);
		result = q1.toString();
		expected = "[ 1 ]";
		t = result.equals(expected);
		verify(t, "Queue was not mergeSorted properly: " + result + "\nExpected " + expected);

		q1 = new LinkedQueue();	// Case: standard queue.
		q1.enqueue(2);
		q1.enqueue(5);
		q1.enqueue(-1);
		q1.enqueue(0);
		q1.enqueue(1);
		mergeSort(q1);
		result = q1.toString();
		expected = "[ -1 0 1 2 5 ]";
		t = result.equals(expected);
		verify(t, "Queue was not mergeSorted properly: " + result + "\nExpected " + expected);
	}

}
